Lý thuyết đệ quy bắt nguồn từ những năm 1930, với công trình của Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene và Emil Post.[1][2]

Các kết quả cơ bản mà các nhà nghiên cứu thu được đã thiết lập tính toán Turing như là sự chính thức hóa chính xác của ý tưởng không chính thức về tính toán hiệu quả. Những kết quả này đã khiến Stephen Kleene (1952) đặt ra hai tên "Luận án của Church" (Kleene 1952: 300) và "Luận án của Turing" (Kleene 1952: 376). Ngày nay, những điều này thường được coi là một giả thuyết duy nhất, luận án Church-Turing, nói rằng bất kỳ hàm nào có thể tính toán được bằng thuật toán là một hàm tính toán được. Mặc dù ban đầu còn hoài nghi, đến năm 1946, Gôdel đã lập luận ủng hộ luận điểm này: